#include <bits/stdc++.h>

using namespace std;

#define rep(i, x, y) for(int i = (x); i <= (y); i++)
#define per(i, x, y) for(int i = (x); i >= (y); i--)

#define in read()
#define eb emplace_back

int read() {
	int x; scanf("%d", &x); return x;
}

using ull = unsigned long long;

const int N = 110;

int m, n;
char s[N];

mt19937 rnd(time(NULL));

void solve() {
	m = in; scanf("%s", s + 1); n = strlen(s + 1);
	vector < ull > pot;
	rep(i, 'a', 'z') {
		ull ret = 0, cur = 1;
		per(j, n, 1) {
			if(s[j] == i) ret += cur;
			cur = cur * m;
		} if(ret) pot.eb(ret);
	}
	ull ans = 0;
	if(pot.size() != m || m == 1) {
		for(auto v : pot) ans = __gcd(ans, v);
	} else {
		if(m == 2) {
			sort(pot.begin(), pot.end());
			ull ret = 0, ct = 0;
			for(auto v : pot) ret += v * ct, ct++;
			ans = ret;
		} else {
			if(pot[0] > pot[1]) swap(pot[0], pot[1]);
			ull ret = 0, ct = 0;
			for(auto v : pot) ret += v * ct, ct++;
			ans = __gcd(ans, ret);
			auto sub = [&](ull x, ull y) { return x > y ? x - y : y - x; };
			rep(i, 1, int(pot.size()) - 1) ans = __gcd(ans, sub(pot[i], pot[i - 1]));
		}
	} printf("%llu\n", ans);
}

int main() {
	int T = in; while(T--) solve();
}
